package com.liang.leetcode.dp;

/**
 * 518.零钱兑换 II -- 完全背包问题，装满背包最少的物品组合数
 * 凑成总金额有几种凑法
 */
public class Dp11_CoinChange2 {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 5;
        System.out.println(coinChange(coins, amount));
    }

    /**
     * 解法1：动态规划
     *
     * 面值  0  1   2      3       4       5    总金额
     *  1   1  1   11    111     1111    11111
     *
     *  2   1  1   11    111     1111    11111
     *             2     21      211     3111
     *                           22      321
     *
     *  5   1  1   11    111     1111    11111
     *             2     21      211     3111
     *                           22      321
     *                                   5
     * if(放得下){
     *     dp[i][j] = dp[i-1][j] + dp[i][j-coin[i]]
     * } else{
     *     dp[i][j] = dp[i-1][j]
     * }
     */
    private static int coinChange(int[] coins, int amount) {
        // dp[i][j] 表示使用前 i 种硬币凑成金额 j 的硬币组合
        int[][] dp = new int[coins.length][amount + 1];
        // 初始化第一列数据
        for (int i = 0; i < coins.length; i++) {
            dp[i][0] = 1;
        }
        // 先处理第一枚硬币
        for (int j = coins[0]; j <= amount; j++) {
            dp[0][j] = dp[0][j - coins[0]];
        }
        // 从第二枚硬币开始遍历
        for (int i = 1; i < coins.length; i++) {
            // 再遍历背包容量 j
            for (int j = 1; j <= amount; j++) {
                if (j >= coins[i]) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[coins.length - 1][amount];
    }

    /**
     * 滚动数组降维优化
     */
    private static int coinChange2(int[] coins, int amount) {
        // dp[j] 表示凑成金额 j 的硬币组合数
        int[] dp = new int[amount + 1];
        // 初始化 dp 数组
        dp[0] = 1;
        // 遍历硬币 i，[1,2,5]
        for (int i = 0; i < coins.length; i++) {
            // 遍历金额 j 到 amount 5
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] = dp[j] + dp[j - coins[i]];
            }
        }
        return dp[amount];
    }

}
